热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

也就是|算式_入门篇2#复杂度分析(下):浅析最好最坏平均均摊时间复杂度

篇首语:本文由编程笔记#小编为大家整理,主要介绍了入门篇2#复杂度分析(下):浅析最好最坏平均均摊时间复杂度相关的知识,希望对你有一定的参考价值。说明

篇首语:本文由编程笔记#小编为大家整理,主要介绍了入门篇2 # 复杂度分析(下):浅析最好最坏平均均摊时间复杂度相关的知识,希望对你有一定的参考价值。



说明

【数据结构与算法之美】专栏学习笔记。


为什么引入这些时间复杂度

先看下面代码

// n 表示数组 array 的长度
int find(int[] array, int n, int x)
int i = 0;
int pos = -1;
for (; i < n; &#43;&#43;i)
if (array[i] &#61;&#61; x)
pos &#61; i;
break;


return pos;

上面代码中如果没有 break&#xff1b;那么代码的时间复杂度就是 O(n)&#xff0c;但是代码的循环中存在提前退出循环的操作&#xff0c;普通的时间复杂度分析解决不了这个问题。为了表示代码在不同情况下的不同时间复杂度&#xff0c;就引入了最好、最坏、平均、均摊时间复杂度。


最好、最坏情况时间复杂度


  • 最好情况时间复杂度&#xff1a;在最理想的情况下&#xff0c;执行代码的时间复杂度。
  • 最坏情况时间复杂度&#xff1a;在最糟糕的情况下&#xff0c;执行代码的时间复杂度。

上面代码在最理想的情况下&#xff0c;查找的变量 x 正好是数组的第一个元素&#xff0c;时间复杂度就是 O(1)&#xff1b;在最糟糕的情况下&#xff0c;就是把整个数组都遍历一遍&#xff0c;时间复杂度就成了 O(n)。


平均情况时间复杂度

最好、最坏比较极端&#xff0c;为了更好地表示平均情况下的复杂度&#xff0c;引入了平均情况时间复杂度。

平均时间复杂度&#xff1a;又叫加权平均时间复杂度&#xff08;或者期望时间复杂度&#xff09;&#xff0c;用代码在所有情况下执行的次数的加权平均值表示。

上面的代码中查找的变量 x 在数组中的位置&#xff0c;有 n&#43;1 种情况&#xff1a;


  • 在数组的 0&#xff5e;n-1 位置中&#xff1a;n 种
  • 不在数组中&#xff1a;1 种

假设在数组中与不在数组中的概率都为 1/2&#xff0c;那么出现在 0&#xff5e;n-1 中任意位置的概率就是 1/(2n)。


根据下面等差数列的公式&#xff1a;



1&#43;2&#43;3&#43;…&#43;n &#61; n(1&#43;n)/2


可以快速计算出上面计算式等于(3n &#43; 1)/4&#xff0c;推出平均时间复杂度为 O(n)。

大多数情况下&#xff0c;不需要区分最好、最坏、平均情况时间复杂度三种情况。只有同一块代码在不同的情况下&#xff0c;时间复杂度有量级的差距&#xff0c;才会使用这三种复杂度表示法来区分。


均摊时间复杂度

下面看一个往数组中插入数据的例子&#xff1a;当数组满了之后&#xff0c;也就是代码中的 count &#61;&#61; array.length 时&#xff0c;用 for 循环遍历数组求和&#xff0c;并清空数组&#xff0c;将求和之后的 sum 值放到数组的第一个位置&#xff0c;然后再将新的数据插入。但如果数组一开始就有空闲空间&#xff0c;则直接将数据插入数组。这里均摊的话不止一次调用 insert 的&#xff0c;可以理解为有外循环。

int[] array &#61; new int[n];
int count &#61; 0;
void insert(int val)
if (count &#61;&#61; array.length)
int sum &#61; 0;
for (int i &#61; 0; i < array.length; &#43;&#43;i)
sum &#61; sum &#43; array[i];

array[0] &#61; sum;
count &#61; 1;

array[count] &#61; val;
&#43;&#43;count;

最理想的情况下&#xff0c;数组中有空闲空间&#xff0c;时间复杂度为 O(1)&#xff1b;最坏的情况下&#xff0c;数组中没有空闲空间&#xff0c;需要遍历一遍&#xff0c;其时间复杂度为 O(n)。

根据数据插入的位置的不同&#xff0c;可以分为 n 种情况&#xff0c;每种情况的时间复杂度是 O(1)。另外一种在数组没有空闲空间时插入一个数据&#xff0c;时间复杂度是 O(n)。这样就有 n &#43; 1 种情况&#xff1a;得到平均时间复杂度为 O(1)。

这里并不需要像之前的平均复杂度分析方法那样&#xff0c;找出所有的输入情况及相应的发生概率&#xff0c;然后再计算加权平均值。针对这种特殊的场景&#xff0c;就引入了一种更加简单的分析方法均摊时间复杂度&#xff0c;又叫摊还分析&#xff08;或者叫平摊分析&#xff09;。

均摊分析的大致思路&#xff1a;这里对于 insert() 函数来说&#xff0c;O(1) 时间复杂度的插入和 O(n) 时间复杂度的插入&#xff0c;出现的频率是非常有规律的&#xff0c;数组已经满了&#xff0c;也就是 O(n) 是无空闲的状态&#xff0c;每满一次就会清空数组&#xff0c;清空数组后重新开始写 n - 1 次才会进行下一次清空&#xff0c;每次写入的复杂度就是O(1)&#xff0c;有 O(n) 后接着 n - 1 个 O(1)&#xff0c;循环往复。所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上&#xff0c;均摊下来&#xff0c;这一组连续的操作的均摊时间复杂度就是 O(1)&#xff0c;可以理解为 (n &#43; n - 1)/n。

均摊时间复杂度就是一种特殊的平均时间复杂度&#xff0c;能够应用均摊时间复杂度分析的场合&#xff0c;一般均摊时间复杂度就等于最好情况时间复杂度。


推荐阅读
  • 本文详细介绍了Java中vector的使用方法和相关知识,包括vector类的功能、构造方法和使用注意事项。通过使用vector类,可以方便地实现动态数组的功能,并且可以随意插入不同类型的对象,进行查找、插入和删除操作。这篇文章对于需要频繁进行查找、插入和删除操作的情况下,使用vector类是一个很好的选择。 ... [详细]
  • 本文由编程笔记#小编为大家整理,主要介绍了logistic回归(线性和非线性)相关的知识,包括线性logistic回归的代码和数据集的分布情况。希望对你有一定的参考价值。 ... [详细]
  • [大整数乘法] java代码实现
    本文介绍了使用java代码实现大整数乘法的过程,同时也涉及到大整数加法和大整数减法的计算方法。通过分治算法来提高计算效率,并对算法的时间复杂度进行了研究。详细代码实现请参考文章链接。 ... [详细]
  • 本文介绍了使用Java实现大数乘法的分治算法,包括输入数据的处理、普通大数乘法的结果和Karatsuba大数乘法的结果。通过改变long类型可以适应不同范围的大数乘法计算。 ... [详细]
  • 如何用UE4制作2D游戏文档——计算篇
    篇首语:本文由编程笔记#小编为大家整理,主要介绍了如何用UE4制作2D游戏文档——计算篇相关的知识,希望对你有一定的参考价值。 ... [详细]
  • 判断数组是否全为0_连续子数组的最大和的解题思路及代码方法一_动态规划
    本文介绍了判断数组是否全为0以及求解连续子数组的最大和的解题思路及代码方法一,即动态规划。通过动态规划的方法,可以找出连续子数组的最大和,具体思路是尽量选择正数的部分,遇到负数则不选择进去,遇到正数则保留并继续考察。本文给出了状态定义和状态转移方程,并提供了具体的代码实现。 ... [详细]
  • 本文探讨了C语言中指针的应用与价值,指针在C语言中具有灵活性和可变性,通过指针可以操作系统内存和控制外部I/O端口。文章介绍了指针变量和指针的指向变量的含义和用法,以及判断变量数据类型和指向变量或成员变量的类型的方法。还讨论了指针访问数组元素和下标法数组元素的等价关系,以及指针作为函数参数可以改变主调函数变量的值的特点。此外,文章还提到了指针在动态存储分配、链表创建和相关操作中的应用,以及类成员指针与外部变量的区分方法。通过本文的阐述,读者可以更好地理解和应用C语言中的指针。 ... [详细]
  • 2020年第十一届蓝桥杯决赛JAVA B G题“皮亚诺曲线距离“的个人题解目录
    本文是2020年第十一届蓝桥杯决赛JAVA B G题“皮亚诺曲线距离“的个人题解目录。文章介绍了皮亚诺曲线的概念和特点,并提供了计算皮亚诺曲线上两点距离的方法。通过给定的两个点的坐标,可以计算出它们之间沿着皮亚诺曲线走的最短距离。本文还提供了个人题解的目录,供读者参考。 ... [详细]
  • Go语言实现堆排序的详细教程
    本文主要介绍了Go语言实现堆排序的详细教程,包括大根堆的定义和完全二叉树的概念。通过图解和算法描述,详细介绍了堆排序的实现过程。堆排序是一种效率很高的排序算法,时间复杂度为O(nlgn)。阅读本文大约需要15分钟。 ... [详细]
  • Oracle优化新常态的五大禁止及其性能隐患
    本文介绍了Oracle优化新常态中的五大禁止措施,包括禁止外键、禁止视图、禁止触发器、禁止存储过程和禁止JOB,并分析了这些禁止措施可能带来的性能隐患。文章还讨论了这些禁止措施在C/S架构和B/S架构中的不同应用情况,并提出了解决方案。 ... [详细]
  • SpringMVC接收请求参数的方式总结
    本文总结了在SpringMVC开发中处理控制器参数的各种方式,包括处理使用@RequestParam注解的参数、MultipartFile类型参数和Simple类型参数的RequestParamMethodArgumentResolver,处理@RequestBody注解的参数的RequestResponseBodyMethodProcessor,以及PathVariableMapMethodArgumentResol等子类。 ... [详细]
  • 本文介绍了如何在给定的有序字符序列中插入新字符,并保持序列的有序性。通过示例代码演示了插入过程,以及插入后的字符序列。 ... [详细]
  • 图解redis的持久化存储机制RDB和AOF的原理和优缺点
    本文通过图解的方式介绍了redis的持久化存储机制RDB和AOF的原理和优缺点。RDB是将redis内存中的数据保存为快照文件,恢复速度较快但不支持拉链式快照。AOF是将操作日志保存到磁盘,实时存储数据但恢复速度较慢。文章详细分析了两种机制的优缺点,帮助读者更好地理解redis的持久化存储策略。 ... [详细]
  • Oracle分析函数first_value()和last_value()的用法及原理
    本文介绍了Oracle分析函数first_value()和last_value()的用法和原理,以及在查询销售记录日期和部门中的应用。通过示例和解释,详细说明了first_value()和last_value()的功能和不同之处。同时,对于last_value()的结果出现不一样的情况进行了解释,并提供了理解last_value()默认统计范围的方法。该文对于使用Oracle分析函数的开发人员和数据库管理员具有参考价值。 ... [详细]
  • 也就是|小窗_卷积的特征提取与参数计算
    篇首语:本文由编程笔记#小编为大家整理,主要介绍了卷积的特征提取与参数计算相关的知识,希望对你有一定的参考价值。Dense和Conv2D根本区别在于,Den ... [详细]
author-avatar
萱筱璧
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有